In a packet based communication network which supports the simultaneous flow of multiple virtual channels (VC) through each physical communication link, packets or cells (cells are fixed size packets) belonging to different virtual channels will be interleaved as they are transmitted onto the communication link. Whether the origin of the packets or cells is at an end-station directly connected to a communication link or from a switch which is multiplexing multiple incoming links to the same outgoing link, the scheduling of packets or cells onto the outgoing link must be performed in such a way so as to satisfy the negotiated quality of service (QOS) of the virtual channels (VC's) to which they pertain. One example of the type of network described above is the Asynchronous Transfer Mode (ATM) ("Asynchronous Transfer Mode: Solution for Broadband ISDN", M de Prycker, Ellis Horwood, 1991) the internationally agreed upon technique for transmission, multiplexing, and switching in a broadband network. ATM uses fixed size cells as a unit of transmission.
ATM networks are designed to support the integration of high quality voice, video, and high speed data traffic. To the end-user, it promises to provide the ability to transport connection-oriented and connectionless traffic at constant or variable bit rates. It enables the allocation of bandwidth on demand and provides a negotiated Quality-of-Service (QOS). To a network provider, ATM enables the transport of different traffic types through the same network. In order for a network to meet QOS requirements as set by the user for a session, the network must have sufficient information about the traffic characteristics of the session. This may be approximated by (but not limited to) three basic parameters: 1) average transmission rate, 2) peak transmission rate and 3) the interval over which the data may be transmitted at peak rate.
As a part of the QOS contract with network, all sessions must abide by the traffic parameters and not violate these parameters in order for the network to guarantee QOS to all the users. This gives rise to a complex scheduling problem when many sessions are established over a network link, which requires that each session's contract with the network not be violated. At the same time, all sessions must get the desired capacity from the network. This problem is fairly complex particularly when a large number of sessions with a wide range of traffic descriptors are involved. The problem is compounded when different sessions require a different QoS. Therefore, in case of contention, where a multiplicity of sessions have data to be transmitted and their individual contracts with the network will allow them to transmit, sessions requiring stricter QOS guarantee must be given priority over other sessions.
The development of ATM has increased the need to develop methods to efficiently and fairly multiplex multiple virtual channels onto a single physical media. Traffic flow patterns are variable within quality of service contract parameters on a per channel basis. Multiple levels of priority have been defined to differentiate groups of virtual channels. However, scheduling conflicts are likely to occur when aggregating like priority virtual channels since high hardware physical media utilization is required. Schedulers are required to operate in real time and are traditionally memory intensive when channel conflicts occur.
Traditional network scheduling techniques (e.g., Token Ring) (Token Ring Access Method and Physical Layer Specifications, IEEE, 1985) and Ethernet (The Ethernet: A Local Area Network: Data Link Layer and Physical Layer Specifications, Version 2.0, Digital Equipment Corporation, Intel, Xerox, 1982) have a fairly simple notion of traffic. These network scheduling techniques are based on best effort transmission schemes, whereby each user may obtain a fair share of the network bandwidth. There is no pre-negotiated traffic descriptor or Quality-of-Service (QOS) requirements. Users obtain as much of a share of the network bandwidth as possible, and network scheduling distributes the bandwidth fairly between them. The above scheduling techniques are relatively simple and well known (e.g., hierarchical round robin or static priority scheduling). When the network provides a transmission opportunity (e.g., by means of a token in a Token Ring network) to a user, the user will transmit data based on a first-come first-serve policy.
The FDDI Standard (ANSI Standard, "FDDI SMT", ANSI X3T9.5) introduced the notion of negotiated bandwidth wherein the user requests bandwidth by means of specifying only one rate (peak rate) requirement and the network controls when that user may be able to transmit. There is no notion of average rate or burst length. In all these examples of known systems, the networks regulate transmission opportunities based on a simple fairness algorithm.
Due to the large number of virtual channels that may be simultaneously active on an ATM link, the set of active virtual channel contexts may be stored in external memory banks. Memory access bandwidth requirements translate into the need for some number of external memory banks that are physically connected to a VLSI module. The number of input/output pins available to a VLSI module is a scarce commodity and will ultimately limit the aggregation function's ability to scale for high bandwidth ATM applications.
Some systems address the scheduling problem by implementing a finite set of hardware timers dedicated to operate on groups of channels with similar quality of service objectives. This grouping reduces the number of scheduling conflicts by establishing a predefined order within each set of channels. The set of possible scheduling conflicts is reduced to the set of conflicts arising from simultaneous timer events. Such systems have a number of limitations. First, to reduce timer conflicts relatively few timers are used and, consequently, the granularity of the quality of service is course as compared to the set of rates defined by the ATM standard. Second, when timer conflicts occur, the resolution of channel conflicts will be sub-optimal on a per channel basis due to the generalization applied to form timer sets.